package com.ls.day10;

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

public class GenerateParenthesis {

    public static void main(String[] args) {
        List<String> res = generateParenthesis(4);
        for (String s:res){
            System.out.println(s);
        }
    }

    public static List<String> generateParenthesis(int n) {
        List<String> res = new ArrayList<>();
        res.add("()");
        List<String> item = new ArrayList<>();
        List<String> tem;
        for (int i=1;i<n;i++){
            item.clear();
            item.add(res.get(0)+"()");
            for (String s:res){
                for (int j=0;j<s.length();j++){
                    if (s.charAt(j)=='('){
                        StringBuilder ss = new StringBuilder(s);
                        item.add(ss.insert(j+1,"()").toString());
                    }
                }
            }
            tem = res;
            res=item;
            item=tem;
        }
        HashSet<String> set = new HashSet<>();
        set.addAll(res);
        res.clear();
        res.addAll(set);
        return res;
    }
}
